package com.c2b.algorithm.newcoder.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=295&tqId=644&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">求二叉树的层序遍历</a>
 * <p>给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）</p>
 * <pre>
 *     例如：给定的二叉树是{3,9,20,#,#,15,7},
 *              3
 *             / \
 *            9   20
 *               / \
 *              15  7
 *     该二叉树层序遍历的结果是：[[3],[9,20],[15,7]]
 * </pre>
 *
 * @author c2b
 * @since 2023/3/13 17:25
 */
public class BM0026LevelOrder_M {

    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 当前层最后一个节点
        TreeNode currLevelLastNode = root;
        // 下一层的最后一个节点
        TreeNode nextLevelLastNode = null;
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            arrayList.add(node.val);
            // 对于当前层所有节点的子节点，成为下一层的最后一个节点
            if (node.left != null) {
                queue.offer(node.left);
                nextLevelLastNode = node.left;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextLevelLastNode = node.right;
            }
            // 如果是当前层的最后一个节点,把所有的节点汇总
            if (node == currLevelLastNode) {
                resList.add(arrayList);
                arrayList = new ArrayList<>();
                currLevelLastNode = nextLevelLastNode;
                nextLevelLastNode = null;
            }
        }
        return resList;
    }

    public ArrayList<ArrayList<Integer>> levelOrder2(TreeNode root) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            // 把当前层的所有节点弹出，下一层的所有节点入队
            final int currLevelNodeCount = queue.size();
            for (int i = 0; i < currLevelNodeCount; i++) {
                TreeNode node = queue.poll();
                arrayList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            resList.add(arrayList);
        }
        return resList;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        treeNode1.left = new TreeNode(2);
        treeNode1.right = new TreeNode(3);
        treeNode1.left.left = new TreeNode(4);
        treeNode1.left.right = new TreeNode(5);
        //treeNode1.right.left = new TreeNode(15);
        //treeNode1.right.right = new TreeNode(7);
        TreeNode treeNode2 = new TreeNode(1);
        treeNode2.left = new TreeNode(2);
        BM0026LevelOrder_M bm0026LevelOrder_m = new BM0026LevelOrder_M();
        for (ArrayList<Integer> arrayList : bm0026LevelOrder_m.levelOrder(treeNode1)) {
            for (Integer integer : arrayList) {
                System.out.println(integer);
            }
        }
    }
}
